#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdio.h>
#include<stack>
#include<queue>
#include<cstring>
#include<unordered_map>
#include<malloc.h>

using namespace std;

//第一题------------------------------------------------------------------------------
bool gcd(int x, int y){
    return x ? gcd(y % x, x) : y;    
}

//开始总共只有两种倒法，十升向7升的到，十升向3升的到，然后不回倒，下一步倒向另一个，直到有解为止
int pull(int m, int n) {
	int ten = m + n, a = 0, b = 0; //每一个壶的初始升数,a，b代表两个壶，当m为3时，a为3L壶；m为7时，a为7L壶
	int total = 0;
	cout << total ++ << ": " << ten << " " << a << " " << b << endl;
	while(ten != m + n >> 1){
	    if(a == 0){
	        //当m为3时，a为3L壶；m为7时，a为7L壶
	        ten -= m;
	        a += m;
	        cout << total ++ << ": " << ten << " " << a << " " << b << endl;
	    }
	    if(a > 0 && b < n){
	        //判断m是7还是n是7，及b=7时能否给满
	        if(a + b <= n){
	            b += a;
	            a -= a;
	            cout << total ++ << ": " << ten << " " << a << " " << b << endl;
	        } 
	        else {
	            a -= n - b;
	            b = n;
	            cout << total ++ << ": " << ten << " " << a << " " << b << endl;
	        }
	    }
	    if(b == n){
	        b -= n;
	        ten += n;
	        cout << total ++ << ": " << ten << " " << a << " " << b << endl;
	    }
	    
	    if(m >= n && a == m + n >> 1)break;
	    if(m <= n && b == m + n >> 1)break;
	}
} 

void text1(){
    int m = 7, n = 3;
    if(!(m + n) % gcd(m , n) || (m + n) & 1){
        cout << "None" << endl;
        return ;
    }
	int min1, min2;
	cout << "第 1 种方案：" << endl;
	min1 = pull(m , n);
	cout << "------------------------" << endl;
	cout << "第 2 种方案：" << endl; 
	min2 = pull(n , m);
	cout << "------------------------" << endl;
	if (min1 > min2)
		cout << "第 2 种方案步骤最少。" << endl; 
	else cout << "第 1 种方案步骤最少。" << endl; 
	cout << endl << endl << endl;
	return ; 
}

//第二题--栈方法-----------------------------------------------------------------------
int map02[9][9] = {
	{0, 0, 5,  3, 0, 0,  0, 0, 0},
	{8, 0, 0,  0, 0, 0,  0, 2, 0},
	{0, 7, 0,  0, 1, 0,  5, 0, 0},

	{4, 0, 0,  0, 0, 5,  3, 0, 0},
	{0, 1, 0,  0, 7, 0,  0, 0, 6},
	{0, 0, 3,  2, 0, 0,  0, 8, 0},

	{0, 6, 0,  5, 0, 0,  0, 0, 9},
	{0, 0, 4,  0, 0, 0,  0, 3, 0},
	{0, 0, 0,  0, 0, 9,  7, 0, 0}
};//初始化

//检查每一个九宫格时，每次都定位在(x, y)所在的 九宫格的中心 ，然后才开始向周围遍历
int x02[9] = { -1, -1, -1, 0,  0, 0,  1, 1, 1 };
int y02[9] = { -1,  0,  1, -1, 0, 1, -1, 0, 1 };

stack<int> stk02;//保存的是做出修改的空格的下标（1~81）
//只有当后面的格子中出现了无论如何都不能实现的情况，才会回溯回来

void print_shudu()
{
	cout << "数独的解为：" << endl;
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cout << map02[i][j] << " ";
			if ((j + 1) % 3 == 0) cout << " ";
		}
		cout << endl;
		if ((i + 1) % 3 == 0) cout << endl;
	}
}

bool check02(int x, int y, int num)//查询 (x, y) 填入数字 num 是否可行
{
	//检查行、列
	for (int i = 0; i < 9; i++)
	{
		if (map02[i][y] == num) //第 y 列有数字 num
			return false;//填入数字 num 不可行
		if (map02[x][i] == num) //第 x 行有数字 num
			return false;
	}

	//检查(x, y)所在的九宫格
	int center_x = x / 3 * 3 + 1;//寻找中心
	int center_y = y / 3 * 3 + 1;
	for (int i = 0; i < 9; i++)
	{
		int tmpx = center_x + x02[i];
		int tmpy = center_y + y02[i];

		if (map02[tmpx][tmpy] == num) return false;
		else continue;
	}

	return true;//都检查完了还是没有因为错误返回
}

int find_space()//查找下一个可填入的位置, 从loc开始查找
{
	for (int i = 0; i < 81; i++)
	{
		int x = i / 9;
		int y = i % 9;

		if (map02[x][y] == 0)
			return i;
	}

	return -1;//也可能没有找到空格，这象征着数独问题解的结束
}

bool shudu()
{
	stk02.push(find_space());//寻找空格

	int num;
	while (stk02.top() >= 0)
	{
		int loc = stk02.top();//查看空格
		int x = loc / 9;
		int y = loc % 9;

		num = map02[x][y] + 1;
		while (num <= 9 && check02(x, y, num) == false)num ++ ;

		if (num > 9)
		{
			stk02.pop();//无法匹配，弹出空格，说明上面的步骤出了问题
			map02[x][y] = 0;//重置
		}
		else
		{
			map02[x][y] = num;
			stk02.push(find_space());//继续寻找下一个空格
		}

	}

	if (stk02.empty() == true)//如果栈为空，说明已经把所有情况都试过了，回退到了最开始的位置
	{
		return false;
	}
	else
	{
		return true;
	}

}



//第二题--DFS方法----------------------------------------------------------------------
const int N = 9, M = 1 << N;

int ones[M], map[M];
int row[N], col[N], cell[3][3];
int arr[9][9] = {
	{0, 0, 5,  3, 0, 0,  0, 0, 0},
	{8, 0, 0,  0, 0, 0,  0, 2, 0},
	{0, 7, 0,  0, 1, 0,  5, 0, 0},

	{4, 0, 0,  0, 0, 5,  3, 0, 0},
	{0, 1, 0,  0, 7, 0,  0, 0, 6},
	{0, 0, 3,  2, 0, 0,  0, 8, 0},

	{0, 6, 0,  5, 0, 0,  0, 0, 9},
	{0, 0, 4,  0, 0, 0,  0, 3, 0},
	{0, 0, 0,  0, 0, 9,  7, 0, 0}
};

void init()
{
    for (int i = 0; i < N; i ++ )
        row[i] = col[i] = (1 << N) - 1;

    for (int i = 0; i < 3; i ++ )
        for (int j = 0; j < 3; j ++ )
            cell[i][j] = (1 << N) - 1;
}

void draw(int x, int y, int t, bool is_set)
{
    if (is_set) arr[x][y] = 1 + t;
    else arr[x][y] = 0;

    int v = 1 << t;
    if (!is_set) v = -v;

    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v;
}

int lowbit(int x)
{
    return x & -x;
}

int get(int x, int y)
{
    return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt)
{
    if (!cnt) return true;

    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (arr[i][j] == 0)
            {
                int state = get(i, j);
                if (ones[state] < minv)
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true;
        draw(x, y, t, false);
    }

    return false;
}






//第三题------------------------------------------------------------------------------
const int SailPlace = 4, CreatePlace = 3;//N代表销地， M代表产地

int B03[SailPlace] = { 3, 6, 5, 6 };//N个销地
int A03[CreatePlace] = { 7, 4, 9 };//M个产地
int judgeA03[CreatePlace] = { 7, 4, 9 };

int back03[CreatePlace+1][SailPlace+1];//存储备用方案
//int ans03[CreatePlace][SailPlace];//存储最优方案

int ui_vj[CreatePlace + 1][SailPlace + 1];//存储位势表（ui+vj）表， 多出来的一行存储位势
int space_check[CreatePlace][SailPlace];

//逆时针坐标变化
//             上  左  下  右
//             0   1   2   3
int x03[5] = { 0, -1,  0,  1 };
int y03[5] = { 1,  0, -1,  0 };

//M行N列运价表
int priceij[CreatePlace][SailPlace] =
{
	{3, 11, 3 , 10},
	{1, 9 , 2 , 8 },
	{7, 4 , 10, 5 }
};

//i->j每个单位的运价
struct price
{
	int i;//ai地为销地
	int j;//bj地为产地
	int cij;//ai地运向bj地 的单位价格

	bool operator < (const price& other) const//自定义排序
	{
		return cij < other.cij;
	}
};

//记录回路上的顶点
struct Point
{
	int ii, jj;//坐标
	int num;//运输量
	int xuhao;//回路上的序号
};

//每一次回路的数据
struct loop
{
	int start_deri; // 出发的方向 （1\2\3\4）
	int i, j;//出发点空格的坐标
	vector<Point> path;//记录回路经过的顶点
	//物理下标是从0开始的
	//逻辑下标是从1开始的

};

vector<loop> vlopp;

// 自定义比较类
struct ComparePrice
{
	bool operator()(const price& a, const price& b) const
	{
		return a.cij > b.cij;
	}
};

//priority_queue<price, vector<price>, greater<price>> qu03; //最小堆
priority_queue<price, vector<price>, ComparePrice> qu03; //最小堆

bool stB[SailPlace];//标记每一列是否被划掉，如果stB[i] == false(表示被划掉), 说明B[i] == 0, 表示bi销地已经不需要进货了
bool stA[CreatePlace];//标记每一行是否被划掉，如果stA[i] == false(表示被划掉), 说明A[i] == 0, 表示ai产地已经不能再出货了


void print()
{
	cout << "最优可行方案如下：" << endl;

	cout << "     B1   B2   B3   B4   " << endl;

	for (int i = 0; i < CreatePlace; i++)
	{
		cout << "A" << i + 1 << "   ";
		for (int j = 0; j < SailPlace; j++)
		{
			printf("%-5d", back03[i][j]);
		}
		cout << endl;
	}
	
	cout << endl;
	cout << "总费用为：";
	int sum = 0, sumIscal = 0;
	int sumCreate = 0;
	for(int i = 0; i < CreatePlace; i ++ )sumCreate += judgeA03[i];
	for(int i = 0; i < CreatePlace; i ++ ){
	    for(int j = 0; j < SailPlace; j ++ ){
	        if(back03[i][j]){
	            cout << back03[i][j] << " * " << priceij[i][j];
	            sum += back03[i][j] * priceij[i][j];
	            sumIscal += back03[i][j];
	            if(sumIscal < sumCreate)cout << " + ";
	            else{
	                cout << " = " << sum << endl;
	                break;
	            }
	        }
	    }
	}
}


//最小元素法
void findmin()
{
	memset(stB, true, sizeof stB);
	memset(stA, true, sizeof stA);//初始时刻，都没有被划掉
	int cnt = SailPlace + CreatePlace;//计数器

	while (cnt && !qu03.empty())//cnt == 0时退出
	{
		price p = qu03.top();//取出最小的
		qu03.pop();

		if (stB[p.j] == true && stA[p.i] == true)
		{
			if (A03[p.i] > B03[p.j])
			{
				back03[p.i][p.j] = B03[p.j];

				A03[p.i] -= B03[p.j];
				B03[p.j] = 0;//Bj不再有需求，而产地Ai还有剩余的货物
				stB[p.j] = false;
				cnt--;
			}
			else if (A03[p.i] == B03[p.j])
			{
				back03[p.i][p.j] = B03[p.j];

				A03[p.i] = 0;
				B03[p.j] = 0;
				stA[p.i] = false;
				stB[p.j] = false;
				cnt--;
			}
			else
			{
				back03[p.i][p.j] = A03[p.i];

				B03[p.j] -= A03[p.i];
				A03[p.i] = 0;//Ai现有的货物全部运往Bj, Bj任然有需求
				stA[p.i] = false;
				cnt--;
			}

		}
	}
}

//利用位势法求解最优方案
void Weishifa()
{
	memset(ui_vj, 0, sizeof(ui_vj));
	memset(stB, true, sizeof stB);//vj, 列位势
	memset(stA, true, sizeof stA);//ui, 行位势
	//初始时刻，所有位势都是可覆写的
	//当被计算一次之后便不可再计算

	ui_vj[0][SailPlace] = 0;//假设u1 == 0
	stA[0] = false;

	//从前往后 遍历不一定能够保证所所有位势均可一次性遍历完整，需要二次遍历
	//从后往前 一定能保证 一次遍历就能够求出所有位势
	for (int i = 0; i < CreatePlace; i++)
	{
		for (int j = SailPlace - 1; j >= 0; j--)
		{
			if (back03[i][j] != 0)//基变量（非零格）求解位势
			{
				if (stA[i] == true)//ui
				{
					stA[i] = false;
					ui_vj[i][SailPlace] = priceij[i][j] - ui_vj[CreatePlace][j];//ui = cij - vj
				}
				else if (stB[j] == true)
				{
					stB[j] = false;
					ui_vj[CreatePlace][j] = priceij[i][j] - ui_vj[i][SailPlace];
				}
				else
				{
					cout << "错误！" << endl;
				}
			}
		}
	}

}

void Space_weishi()
{
	for (int i = 0; i < CreatePlace; i++)
	{
		for (int j = 0; j < SailPlace; j++)
		{
			if (back03[i][j] == 0)//可行解的空格处
			{
				ui_vj[i][j] = ui_vj[CreatePlace][j] + ui_vj[i][SailPlace];
			}
		}
	}
}

void CheckSpace()//空格的检验数表
{
	//如果某个检验格子的值 小于 0， 证明还可以再优化
	//如果某个检验格子的值 等于 0， 证明有多重解
	//如果某个检验格子的值 大于 0， 证明这个位置已经时最优解了，任何变化都将引起总运输费用的上升
	//后续步骤多一步处理

	memset(space_check, 0, sizeof(space_check));

	for (int i = 0; i < CreatePlace; i++)
	{
		for (int j = 0; j < SailPlace; j++)
		{
			if (ui_vj[i][j] != 0)
			{
				space_check[i][j] = priceij[i][j] - ui_vj[i][j];
			}
			else
			{
				//排除非空格（基变量）的影响
				space_check[i][j] = 0x3f3f3f;
			}
		}
	}

}

void loop_find(int, int);

//回路法求解调整路径
void loop_best()//回路法求解最优路径
{
	for (int i = 0; i < CreatePlace; i++)
	{
		for (int j = 0; j < SailPlace; j++)//遍历空格检验表寻找小于0的检验数，然后优化对应的回路
		{
			if (space_check[i][j] < 0)//找到目标检验数
			{
				loop_find(i, j);//开始寻找回路并优化
			}
		}
	}
}

void loop_find(int x, int y)
{
	int cnt = 1;//记录真实的顶点个数
	int pt;//循环控制变量，记录对应的方向，帮助下一步的方向判断

	int xx, yy;

	Point pmin;
	pmin.num = 1e8;

	loop Loop;//只需要找到一个回路
	Loop.path.push_back({ x, y, back03[x][y], 1 });

	for (int i = 0; i < 4; i++)//每一种最初的方向都看一遍
	{
		cnt = 1;
		pt = i;//记录出发的方向
		xx = x + x03[i];
		yy = y + y03[i];

		//一个空格有且仅有一个回路
		if (xx == x && yy == y)//一个空格找到一个回路就可以了
		{
			break;
		}

		while (xx >= 0 && xx < CreatePlace && yy >= 0 && yy <= SailPlace) //不出界并且没找到回路
		{
			if (back03[xx][yy] == 0)//没有碰到数字顶点
			{
				xx = xx + x03[pt];//沿着pt的方向一直走下去
				yy = yy + y03[pt];

				if (xx == x && yy == y) break;
			}
			else
			{
				cnt++;//找到了回路的一个顶点
				pt = (pt + 1) % 4;//换个方向

				Point p;
				p.ii = xx;
				p.jj = yy;
				p.num = back03[xx][yy];
				p.xuhao = cnt;

				Loop.path.push_back(p);

				if (cnt % 2 == 0 && pmin.num > p.num)//偶数顶点 && 找到更小的
				{
					pmin = p;
				}

				xx = xx + x03[pt];
				yy = yy + y03[pt];

				if (xx == x && yy == y) break;

			}

		}

		if (xx < 0 || xx >= CreatePlace || yy < 0 || yy >= SailPlace) //出界 是因为出界而不是因为没有找到回路
		{
			while (cnt != 1)
			{
				Loop.path.pop_back();//弹出无效数据
				cnt--;
			}
		}


	}

	while (Loop.path.empty() == false)
	{
		auto vtmp = Loop.path.back();
		Loop.path.pop_back();

		if (vtmp.xuhao % 2 != 0)//奇数位
		{
			vtmp.num += pmin.num;
			back03[vtmp.ii][vtmp.jj] = vtmp.num;
		}
		else //偶数位
		{
			vtmp.num -= pmin.num;
			back03[vtmp.ii][vtmp.jj] = vtmp.num;
		}

	}
}

void text_2(){
    bool res02 = shudu();
	if (res02 == true)
	{
		print_shudu();
	}
	else
	{
		cout << "该数独问题无解!!!" << endl;
	}
}

void text_2_DFS(){
    for (int i = 0; i < N; i ++ ) map[1 << i] = i;
    for (int i = 0; i < 1 << N; i ++ ){
        int s = 0 ;
        for(int j = 0; j; j -= lowbit(j))s ++ ;
        ones[i] = s;
    }
        
    init();

    int cnt = 0; 
    for (int i = 0; i < N; i ++ )
        for (int j = 0; j < N; j ++ )
            if (arr[i][j] != 0)
            {
                int t = arr[i][j] - 1;
                draw(i, j, t, true);
            }
            else cnt ++ ;

    if(dfs(cnt))for(int i = 0; i < N; i ++ ){
        for(int j = 0; j < N; j ++ ){
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
    else cout << "None";
    cout << "----------------------------------------------------------";
}

void text_3(){
    for (int i = 0; i < CreatePlace; i++)
	{
		for (int j = 0; j < SailPlace; j++)
		{
			price tmp;
			tmp.i = i;
			tmp.j = j;
			tmp.cij = priceij[i][j];

			qu03.push(tmp);
		}
	}

	findmin();//使用最小元素法求出一种可行解
	Weishifa();//求解行位势和列位势
	Space_weishi();//求解空格（非基变量）的（ui+vj)
	CheckSpace();//空格的检验数表
	loop_best();//回路法求解最优路径
	print();
}


int main(){
    cout << "第 一 题 ----------------------------------------------------------" << endl;
    text1();
    
    cout << "第 二 题 ----------------------------------------------------------" << endl;
	cout << "\n";
	text_2();
// 	cout << "----------------------------------------------------------" << endl;
//     text_2_DFS();
	
    cout << "第 三 题 ----------------------------------------------------------" << endl;
	cout << endl;
    text_3();
	

	return 0;
    
}
